We investigate issues related to two hard problems related to voting, theoptimal weighted lobbying problem and the winner problem for Dodgson elections.Regarding the former, Christian et al. [CFRS06] showed that optimal lobbying isintractable in the sense of parameterized complexity. We provide an efficientgreedy algorithm that achieves a logarithmic approximation ratio for thisproblem and even for a more general variant--optimal weighted lobbying. Weprove that essentially no better approximation ratio than ours can be provenfor this greedy algorithm. The problem of determining Dodgson winners is known to be complete forparallel access to NP [HHR97]. Homan and Hemaspaandra [HH06] proposed anefficient greedy heuristic for finding Dodgson winners with a guaranteedfrequency of success, and their heuristic is a ``frequently self-knowinglycorrect algorithm.'' We prove that every distributional problem solvable inpolynomial time on the average with respect to the uniform distribution has afrequently self-knowingly correct polynomial-time algorithm. Furthermore, westudy some features of probability weight of correctness with respect toProcaccia and Rosenschein's junta distributions [PR07].
展开▼
